{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Visited Cells in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #union-find #binary-indexed-tree #segment-tree #array #binary-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #并查集 #树状数组 #线段树 #数组 #二分查找 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumVisitedCells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网格图中最少访问的格子数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的&nbsp;<code>m x n</code>&nbsp;整数矩阵&nbsp;<code>grid</code>&nbsp;。你一开始的位置在&nbsp;<strong>左上角</strong>&nbsp;格子&nbsp;<code>(0, 0)</code>&nbsp;。</p>\n",
    "\n",
    "<p>当你在格子&nbsp;<code>(i, j)</code>&nbsp;的时候，你可以移动到以下格子之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>满足 <code>j &lt; k &lt;= grid[i][j] + j</code>&nbsp;的格子&nbsp;<code>(i, k)</code>&nbsp;（向右移动），或者</li>\n",
    "\t<li>满足 <code>i &lt; k &lt;= grid[i][j] + i</code>&nbsp;的格子&nbsp;<code>(k, j)</code>&nbsp;（向下移动）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回到达 <strong>右下角</strong>&nbsp;格子&nbsp;<code>(m - 1, n - 1)</code>&nbsp;需要经过的最少移动格子数，如果无法到达右下角格子，请你返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/01/25/ex1.png\" style=\"width: 271px; height: 171px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>上图展示了到达右下角格子经过的 4 个格子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/01/25/ex2.png\" style=\"width: 271px; height: 171px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>上图展示了到达右下角格子经过的 3 个格子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/01/26/ex3.png\" style=\"width: 181px; height: 81px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[2,1,0],[1,0,0]]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>无法到达右下角格子。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt; m * n</code></li>\n",
    "\t<li><code>grid[m - 1][n - 1] == 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-visited-cells-in-a-grid](https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-visited-cells-in-a-grid](https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]', '[[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]', '[[2,1,0],[1,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]  # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []  # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key=lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "\n",
    "                mn += 1  # 加上 (i,j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left\n",
    "        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]  # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []  # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key=lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "\n",
    "                mn += 1  # 加上 (i,j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left\n",
    "        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]  # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []  # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key=lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "\n",
    "                mn += 1  # 加上 (i,j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left\n",
    "        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]  # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []  # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key=lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "\n",
    "                mn += 1  # 加上 (i,j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left\n",
    "        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]  # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []  # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key=lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "\n",
    "                mn += 1  # 加上 (i,j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left\n",
    "        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        col_mono = [[] for _ in range(n)]\n",
    "        for i in range(m-1,-1,-1):\n",
    "            cur_row_mono = []\n",
    "            for j in range(n-1,-1,-1):\n",
    "                cur_col_mono= col_mono[j]\n",
    "                dp = inf\n",
    "                g = grid[i][j]\n",
    "                if i==m-1 and j==n-1:\n",
    "                    dp = 0\n",
    "                elif g:\n",
    "                    k = bisect_left(cur_row_mono, -(j+g), key=lambda p:p[1])\n",
    "                    if k<len(cur_row_mono): dp = min(dp,cur_row_mono[k][0])\n",
    "                    k = bisect_left(cur_col_mono, -(i+g), key=lambda p:p[1])\n",
    "                    if k<len(cur_col_mono): dp = min(dp,cur_col_mono[k][0])\n",
    "                if dp==inf: continue\n",
    "            \n",
    "                dp+=1\n",
    "                while cur_row_mono and dp<=cur_row_mono[-1][0]:\n",
    "                    cur_row_mono.pop()\n",
    "                cur_row_mono.append((dp,-j))\n",
    "                while cur_col_mono and dp<=cur_col_mono[-1][0]:\n",
    "                    cur_col_mono.pop()\n",
    "                cur_col_mono.append((dp,-i))\n",
    "        return dp if dp<inf else -1\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]  # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []  # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key=lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "\n",
    "                mn += 1  # 加上 (i,j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left\n",
    "        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]  # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []  # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key=lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "\n",
    "                mn += 1  # 加上 (i,j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left\n",
    "        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]  # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []  # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key=lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "\n",
    "                mn += 1  # 加上 (i,j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left\n",
    "        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]  # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []  # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key=lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "\n",
    "                mn += 1  # 加上 (i,j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left\n",
    "        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)] # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = [] # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1: # 特殊情况，已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key = lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key = lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "            \n",
    "                mn += 1 # 加上 (i, j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j)) # 保证下标单调递增，方便调用bisect_left\n",
    "                while st2 and mn < st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i)) # 保证下标单调递增，方便调用bisect_left\n",
    "        return mn if mn < inf else -1 # 最后一个算出的mn就是f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m , n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = []\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1:\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    k = bisect_left(st, -(j + g), key = lambda p : p[1])\n",
    "                    if k < len(st):\n",
    "                        mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key = lambda p : p[1])\n",
    "                    if k < len(st2) : \n",
    "                        mn = min(mn, st2[k][0])\n",
    "                if mn == inf : continue\n",
    "            \n",
    "                mn += 1\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j))\n",
    "                while st2 and mn <= st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i))\n",
    "        return mn if mn < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        def search(st,i):\n",
    "            left=0\n",
    "            right=len(st)-1\n",
    "            while left<=right:\n",
    "                mid=left+(right-left)//2\n",
    "                if st[mid][1]<=i:\n",
    "                    right=mid-1\n",
    "                else:\n",
    "                    left=mid+1\n",
    "            return left\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        col_st=[[] for _ in range(n)]\n",
    "        for i in range(m-1,-1,-1):\n",
    "            row=grid[i]\n",
    "            st=[]\n",
    "            for j in range(n-1,-1,-1):\n",
    "                g=row[j]\n",
    "                st2=col_st[j]\n",
    "                mn=inf\n",
    "                if i==m-1 and j==n-1:\n",
    "                    mn=0\n",
    "                elif g:\n",
    "                    k=j+g\n",
    "                    k=search(st,k)\n",
    "                    if k<len(st):mn=min(mn,st[k][0])\n",
    "\n",
    "                    k=i+g\n",
    "                    k=search(st2,k)\n",
    "                    if k<len(st2):mn=min(mn,st2[k][0])\n",
    "                if mn<inf: mn+=1\n",
    "                while st and mn<=st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn,j))\n",
    "                while st2 and mn<st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn,i))\n",
    "        return mn if mn<inf else -1\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        # 只能向下或向右移动：\n",
    "        # 最少移动格子数：\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col_st = [[] for _ in range(n)] # 每列的单调栈\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            st = [] # 当前行的单调栈\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                st2 = col_st[j]\n",
    "                mn = inf\n",
    "                g = grid[i][j]\n",
    "                if i == m - 1 and j == n - 1: # 特殊情况，已经是终点\n",
    "                    mn = 0\n",
    "                elif g:\n",
    "                    # 在单调栈上二分\n",
    "                    k = bisect_left(st, -(j + g), key = lambda p: p[1])\n",
    "                    if k < len(st): mn = min(mn, st[k][0])\n",
    "                    k = bisect_left(st2, -(i + g), key = lambda p: p[1])\n",
    "                    if k < len(st2): mn = min(mn, st2[k][0])\n",
    "                if mn == inf: continue\n",
    "            \n",
    "                mn += 1 # 加上 (i, j) 这个格子\n",
    "                # 插入单调栈\n",
    "                while st and mn <= st[-1][0]:\n",
    "                    st.pop()\n",
    "                st.append((mn, -j)) # 保证下标单调递增，方便调用bisect_left\n",
    "                while st2 and mn < st2[-1][0]:\n",
    "                    st2.pop()\n",
    "                st2.append((mn, -i)) # 保证下标单调递增，方便调用bisect_left\n",
    "        return mn if mn < inf else -1 # 最后一个算出的mn就是f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[inf for _ in range(n)] for _ in range(m)]\n",
    "        mini=[[] for _ in range(n)]\n",
    "        # print(grid)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            minj=[]\n",
    "            for j in range(n-1,-1,-1):\n",
    "                # print(i,j)\n",
    "                if i==m-1 and j==n-1:\n",
    "                    dp[i][j]=1\n",
    "                elif grid[i][j]==0:\n",
    "                    dp[i][j]=inf\n",
    "                else:\n",
    "                    minstep=inf\n",
    "                    if j<n-1:\n",
    "                        t=bisect_left(minj, -(j + grid[i][j]), key=lambda p: p[1])\n",
    "                        # print(t)\n",
    "                        minstep=min(minstep,minj[t][0])\n",
    "                    if i<m-1:\n",
    "                        t=bisect_left(mini[j], -(i + grid[i][j]), key=lambda p: p[1])\n",
    "                        # print(t)\n",
    "                        minstep=min(minstep,mini[j][t][0])\n",
    "                    dp[i][j]=minstep+1\n",
    "                \n",
    "                # print(minj, mini[j])\n",
    "                add=(dp[i][j], -j)\n",
    "                while len(minj)>0 and minj[-1][0]>=add[0]:\n",
    "                    minj.pop(-1)\n",
    "                minj.append(add)\n",
    "\n",
    "                add=(dp[i][j], -i)\n",
    "                while len(mini[j])>0 and mini[j][-1][0]>=add[0]:\n",
    "                    mini[j].pop(-1)\n",
    "                mini[j].append(add)\n",
    "                # print(minj, mini[j])\n",
    "\n",
    "        return dp[0][0] if dp[0][0]!=inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[inf for _ in range(n)] for _ in range(m)]\n",
    "        mini=[[] for _ in range(n)]\n",
    "        # print(grid)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            minj=[]\n",
    "            for j in range(n-1,-1,-1):\n",
    "                # print(i,j)\n",
    "                if i==m-1 and j==n-1:\n",
    "                    dp[i][j]=1\n",
    "                elif grid[i][j]==0:\n",
    "                    dp[i][j]=inf\n",
    "                else:\n",
    "                    minstep=inf\n",
    "                    if j<n-1:\n",
    "                        t=bisect_left(minj, -(j + grid[i][j]), key=lambda p: p[1])\n",
    "                        # print(t)\n",
    "                        minstep=min(minstep,minj[t][0])\n",
    "                    if i<m-1:\n",
    "                        t=bisect_left(mini[j], -(i + grid[i][j]), key=lambda p: p[1])\n",
    "                        # print(t)\n",
    "                        minstep=min(minstep,mini[j][t][0])\n",
    "                    dp[i][j]=minstep+1\n",
    "                \n",
    "                # print(minj, mini[j])\n",
    "                add=(dp[i][j], -j)\n",
    "                while len(minj)>0 and minj[-1][0]>=add[0]:\n",
    "                    minj.pop(-1)\n",
    "                minj.append(add)\n",
    "\n",
    "                add=(dp[i][j], -i)\n",
    "                while len(mini[j])>0 and mini[j][-1][0]>=add[0]:\n",
    "                    mini[j].pop(-1)\n",
    "                mini[j].append(add)\n",
    "                # print(minj, mini[j])\n",
    "\n",
    "        return dp[0][0] if dp[0][0]!=inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        f = [[0x3f3f3f3f] * m for _ in range(n)]\n",
    "        f[0][0] = 1\n",
    "        row = [0] * n \n",
    "        col = [0] * m\n",
    "        dq = deque()\n",
    "        dq.append((0, 0))\n",
    "        while dq:\n",
    "            x, y = dq.popleft()\n",
    "\n",
    "            if x == n - 1 and y == m - 1: \n",
    "                return f[x][y]\n",
    "\n",
    "            num = grid[x][y]\n",
    "            oldi, oldj = col[y], row[x]\n",
    "            row[x] = max(row[x], min(y + num, m - 1))\n",
    "            col[y] = max(col[y], min(n - 1, x + num))\n",
    "\n",
    "            for j in range(max(oldj - 10, y), min(m, row[x] + 1)):\n",
    "                if f[x][y] + 1 < f[x][j]:\n",
    "                    f[x][j] = f[x][y] + 1\n",
    "                    dq.append((x, j))\n",
    "                    #print((x, y), \"-->\", (x, j), f[x][j])\n",
    "            \n",
    "            for i in range(max(oldi - 10, x), min(n, col[y] + 1)):\n",
    "                if f[x][y] + 1 < f[i][y]:\n",
    "                    f[i][y] = f[x][y] + 1\n",
    "                    dq.append((i, y))\n",
    "                    #print((x, y), \"-->\", (i, y), f[i][y])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid),len(grid[0])\n",
    "\n",
    "        f= [[-1]*n for _ in range(m)]\n",
    "        a =[[] for _ in range(n)]\n",
    "\n",
    "        f[0][0]=1\n",
    "\n",
    "        for i in range(m):\n",
    "            q = []\n",
    "            for j in range(n):\n",
    "                while len(a[j])>0 and a[j][0][1]<i:\n",
    "                    heapq.heappop(a[j])\n",
    "                \n",
    "                if len(a[j])>0:\n",
    "                    f[i][j]=a[j][0][0]+1\n",
    "                \n",
    "                while len(q)>0 and q[0][1]<j:\n",
    "                    heapq.heappop(q)\n",
    "                if len(q) > 0 and (f[i][j] == -1 or f[i][j] > q[0][0] + 1):\n",
    "                    f[i][j] = q[0][0] + 1\n",
    "                if f[i][j] != -1:\n",
    "                    heapq.heappush(q, (f[i][j], j + grid[i][j]))\n",
    "                    heapq.heappush(a[j], (f[i][j], i + grid[i][j]))\n",
    "        return f[-1][-1]\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row = [[] for _ in range(m)] \n",
    "        col = [[] for _ in range(n)] \n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                r = row[i]\n",
    "                c = col[j]\n",
    "                \n",
    "                while r and r[0][1] < j:\n",
    "                    heapq.heappop(r)\n",
    "\n",
    "                while c and c[0][1] < i:\n",
    "                    heapq.heappop(c)\n",
    "\n",
    "                t = inf \n",
    "                if r:\n",
    "                    t = min(t, r[0][0])\n",
    "                if c:\n",
    "                    t = min(t, c[0][0])\n",
    "                if i == 0 and j == 0:\n",
    "                    t = 0\n",
    "                if i == m-1 and j == n-1:\n",
    "                    return -1 if t == inf else t+1\n",
    "                heapq.heappush(r, (t+1, j+grid[i][j]))\n",
    "                heapq.heappush(c, (t+1, i+grid[i][j]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row = [[] for _ in range(m)] \n",
    "        col = [[] for _ in range(n)] \n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                r = row[i]\n",
    "                c = col[j]\n",
    "                \n",
    "                while r and r[0][1] < j:\n",
    "                    heapq.heappop(r)\n",
    "\n",
    "                while c and c[0][1] < i:\n",
    "                    heapq.heappop(c)\n",
    "\n",
    "                t = inf \n",
    "                if r:\n",
    "                    t = min(t, r[0][0])\n",
    "                if c:\n",
    "                    t = min(t, c[0][0])\n",
    "                if i == 0 and j == 0:\n",
    "                    t = 0\n",
    "                if i == m-1 and j == n-1:\n",
    "                    return -1 if t == inf else t+1\n",
    "                heapq.heappush(r, (t+1, j+grid[i][j]))\n",
    "                heapq.heappush(c, (t+1, i+grid[i][j]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row = [[] for _ in range(m)] \n",
    "        col = [[] for _ in range(n)] \n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                r = row[i]\n",
    "                c = col[j]\n",
    "                \n",
    "                while r and r[0][1] < j:\n",
    "                    heapq.heappop(r)\n",
    "\n",
    "                while c and c[0][1] < i:\n",
    "                    heapq.heappop(c)\n",
    "\n",
    "                t = inf \n",
    "                if r:\n",
    "                    t = min(t, r[0][0])\n",
    "                if c:\n",
    "                    t = min(t, c[0][0])\n",
    "                if i == 0 and j == 0:\n",
    "                    t = 0\n",
    "                if i == m-1 and j == n-1:\n",
    "                    return -1 if t == inf else t+1\n",
    "                heapq.heappush(r, (t+1, j+grid[i][j]))\n",
    "                heapq.heappush(c, (t+1, i+grid[i][j]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row = [[] for _ in range(m)] \n",
    "        col = [[] for _ in range(n)] \n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                r = row[i]\n",
    "                c = col[j]\n",
    "                \n",
    "                while r and r[0][1] < j:\n",
    "                    heapq.heappop(r)\n",
    "\n",
    "                while c and c[0][1] < i:\n",
    "                    heapq.heappop(c)\n",
    "\n",
    "                t = inf \n",
    "                if r:\n",
    "                    t = min(t, r[0][0])\n",
    "                if c:\n",
    "                    t = min(t, c[0][0])\n",
    "                if i == 0 and j == 0:\n",
    "                    t = 0\n",
    "                if i == m-1 and j == n-1:\n",
    "                    return -1 if t == inf else t+1\n",
    "                heapq.heappush(r, (t+1, j+grid[i][j]))\n",
    "                heapq.heappush(c, (t+1, i+grid[i][j]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        f=[[inf]*n for _ in range(m)]\n",
    "        f[0][0]=1\n",
    "        que=deque([(0,0)])\n",
    "        fa_x=[list(range(1,n+5)) for _ in range(m)]\n",
    "        fa_y=[list(range(1,m+5)) for _ in range(n)]\n",
    "        while que:\n",
    "            i,j=que.popleft()\n",
    "            st=[]\n",
    "            p=fa_x[i][j]\n",
    "            while p<n and p-j<=grid[i][j]:\n",
    "                st.append(p)\n",
    "                if f[i][p]==inf:\n",
    "                    f[i][p]=f[i][j]+1\n",
    "                    que.append((i,p))\n",
    "                p=fa_x[i][p]\n",
    "            for q in st:\n",
    "                fa_x[i][q]=p\n",
    "            st=[]\n",
    "            p=fa_y[j][i]\n",
    "            while p<m and p-i<=grid[i][j]:\n",
    "                st.append(p)\n",
    "                if f[p][j]==inf:\n",
    "                    f[p][j]=f[i][j]+1\n",
    "                    que.append((p,j))\n",
    "                p=fa_y[j][p]\n",
    "            for q in st:\n",
    "                fa_y[j][q]=p\n",
    "        #     print(que)\n",
    "        # for i in fa_x:print(i)\n",
    "        # print()\n",
    "        # for i in fa_y:print(i)\n",
    "        # print()\n",
    "        # for i in f:print(i)\n",
    "        # print()\n",
    "        return f[-1][-1] if f[-1][-1]<inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        row = [[] for _ in range(m)]\n",
    "        col = [[] for _ in range(n)]\n",
    "\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        dist[0][0] = 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:\n",
    "                    heappop(row[i])\n",
    "\n",
    "                if row[i]:\n",
    "                    dist[i][j] = min(dist[i][j], row[i][0][0] + 1)\n",
    "\n",
    "                while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:\n",
    "                    heappop(col[j])\n",
    "\n",
    "                if col[j]:\n",
    "                    dist[i][j] = min(dist[i][j], col[j][0][0] + 1)\n",
    "\n",
    "                if dist[i][j] != inf:\n",
    "                    heappush(row[i], (dist[i][j], j))\n",
    "                    heappush(col[j], (dist[i][j], i))\n",
    "\n",
    "        return dist[m - 1][n - 1] if dist[m - 1][n - 1] != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dist = [[-1] * n for _ in range(m)]\n",
    "        dist[0][0] = 1\n",
    "        row, col = [[] for _ in range(m)], [[] for _ in range(n)]\n",
    "\n",
    "        def update(x: int, y: int) -> int:\n",
    "            return y if x == -1 or x > y else x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:\n",
    "                    heapq.heappop(row[i])\n",
    "                if row[i]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[i][row[i][0][1]] + 1)\n",
    "\n",
    "                while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:\n",
    "                    heapq.heappop(col[j])\n",
    "                if col[j]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[col[j][0][1]][j] + 1)\n",
    "\n",
    "                if dist[i][j] != -1:\n",
    "                    heapq.heappush(row[i], (dist[i][j], j))\n",
    "                    heapq.heappush(col[j], (dist[i][j], i))\n",
    "\n",
    "        return dist[m - 1][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dist=[[-1]*n for _ in range(m)]\n",
    "        dist[0][0]=1\n",
    "        row,col=[[]for _ in range(m)],[[]for _ in range(n)]\n",
    "\n",
    "        def update(x:int,y:int)->int:\n",
    "            return y if x==-1 or x>y else x  \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row[i] and row[i][0][1]+grid[i][row[i][0][1]]<j:\n",
    "                    heapq.heappop(row[i])\n",
    "                if row[i]:\n",
    "                    dist[i][j]=update(dist[i][j],dist[i][row[i][0][1]]+1)\n",
    "\n",
    "                while col[j]and col[j][0][1]+grid[col[j][0][1]][j]<i:\n",
    "                    heapq.heappop(col[j])\n",
    "                if col[j]:\n",
    "                    dist[i][j]=update(dist[i][j],dist[col[j][0][1]][j]+1)\n",
    "\n",
    "                if dist[i][j]!=-1:\n",
    "                    heapq.heappush(row[i],(dist[i][j],j))\n",
    "                    heapq.heappush(col[j],(dist[i][j],i))\n",
    "\n",
    "        return dist[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dist = [[-1] * n for _ in range(m)]\n",
    "        dist[0][0] = 1\n",
    "        row, col = [[] for _ in range(m)], [[] for _ in range(n)]\n",
    "\n",
    "        def update(x: int, y: int) -> int:\n",
    "            return y if x == -1 or x > y else x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:\n",
    "                    heapq.heappop(row[i])\n",
    "                if row[i]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[i][row[i][0][1]] + 1)\n",
    "\n",
    "                while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:\n",
    "                    heapq.heappop(col[j])\n",
    "                if col[j]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[col[j][0][1]][j] + 1)\n",
    "\n",
    "                if dist[i][j] != -1:\n",
    "                    heapq.heappush(row[i], (dist[i][j], j))\n",
    "                    heapq.heappush(col[j], (dist[i][j], i))\n",
    "\n",
    "        return dist[m - 1][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dist = [[-1] * n for _ in range(m)]\n",
    "        dist[0][0] = 1\n",
    "        row, col = [[] for _ in range(m)], [[] for _ in range(n)]\n",
    "\n",
    "        def update(x: int, y: int) -> int:\n",
    "            return y if x == -1 or x > y else x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:\n",
    "                    heapq.heappop(row[i])\n",
    "                if row[i]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[i][row[i][0][1]] + 1)\n",
    "\n",
    "                while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:\n",
    "                    heapq.heappop(col[j])\n",
    "                if col[j]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[col[j][0][1]][j] + 1)\n",
    "\n",
    "                if dist[i][j] != -1:\n",
    "                    heapq.heappush(row[i], (dist[i][j], j))\n",
    "                    heapq.heappush(col[j], (dist[i][j], i))\n",
    "\n",
    "        return dist[m - 1][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dist = [[-1] * n for _ in range(m)]\n",
    "        dist[0][0] = 1\n",
    "        row, col = [[] for _ in range(m)], [[] for _ in range(n)]\n",
    "\n",
    "        def update(x: int, y: int) -> int:\n",
    "            return y if x == -1 or x > y else x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:\n",
    "                    heapq.heappop(row[i])\n",
    "                if row[i]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[i][row[i][0][1]] + 1)\n",
    "\n",
    "                while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:\n",
    "                    heapq.heappop(col[j])\n",
    "                if col[j]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[col[j][0][1]][j] + 1)\n",
    "\n",
    "                if dist[i][j] != -1:\n",
    "                    heapq.heappush(row[i], (dist[i][j], j))\n",
    "                    heapq.heappush(col[j], (dist[i][j], i))\n",
    "\n",
    "        return dist[m - 1][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dist = [[-1] * n for _ in range(m)]\n",
    "        dist[0][0] = 1\n",
    "        row, col = [[] for _ in range(m)], [[] for _ in range(n)]\n",
    "\n",
    "        def update(x: int, y: int) -> int:\n",
    "            return y if x == -1 or x > y else x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:\n",
    "                    heapq.heappop(row[i])\n",
    "                if row[i]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[i][row[i][0][1]] + 1)\n",
    "\n",
    "                while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:\n",
    "                    heapq.heappop(col[j])\n",
    "                if col[j]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[col[j][0][1]][j] + 1)\n",
    "\n",
    "                if dist[i][j] != -1:\n",
    "                    heapq.heappush(row[i], (dist[i][j], j))\n",
    "                    heapq.heappush(col[j], (dist[i][j], i))\n",
    "\n",
    "        return dist[m - 1][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dist = [[-1] * n for _ in range(m)]\n",
    "        dist[0][0] = 1\n",
    "        row, col = [[] for _ in range(m)], [[] for _ in range(n)]\n",
    "\n",
    "        def update(x: int, y: int) -> int:\n",
    "            return y if x == -1 or x > y else x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:\n",
    "                    heapq.heappop(row[i])\n",
    "                if row[i]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[i][row[i][0][1]] + 1)\n",
    "\n",
    "                while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:\n",
    "                    heapq.heappop(col[j])\n",
    "                if col[j]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[col[j][0][1]][j] + 1)\n",
    "\n",
    "                if dist[i][j] != -1:\n",
    "                    heapq.heappush(row[i], (dist[i][j], j))\n",
    "                    heapq.heappush(col[j], (dist[i][j], i))\n",
    "\n",
    "        return dist[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dist = [[-1] * n for _ in range(m)]\n",
    "        dist[0][0] = 1\n",
    "        row, col = [[] for _ in range(m)], [[] for _ in range(n)]\n",
    "\n",
    "        def update(x: int, y: int) -> int:\n",
    "            return y if x == -1 or x > y else x\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:\n",
    "                    heapq.heappop(row[i])\n",
    "                if row[i]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[i][row[i][0][1]] + 1)\n",
    "\n",
    "                while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:\n",
    "                    heapq.heappop(col[j])\n",
    "                if col[j]:\n",
    "                    dist[i][j] = update(dist[i][j], dist[col[j][0][1]][j] + 1)\n",
    "\n",
    "                if dist[i][j] != -1:\n",
    "                    heapq.heappush(row[i], (dist[i][j], j))\n",
    "                    heapq.heappush(col[j], (dist[i][j], i))\n",
    "\n",
    "        return dist[m - 1][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row_queues = [[] for _ in range(m)]\n",
    "        col_queues = [[] for _ in range(n)]\n",
    "        dp = [[float('inf')] * n for _ in range(m)]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while row_queues[i] and row_queues[i][0][1] + grid[i][row_queues[i][0][1]] < j:\n",
    "                    heappop(row_queues[i])\n",
    "                if row_queues[i]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][row_queues[i][0][1]] + 1)\n",
    "                \n",
    "                while col_queues[j] and col_queues[j][0][1] + grid[col_queues[j][0][1]][j] < i:\n",
    "                    heappop(col_queues[j])\n",
    "                if col_queues[j]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[col_queues[j][0][1]][j] + 1)\n",
    "                \n",
    "                if dp[i][j] < float('inf'):\n",
    "                    heappush(row_queues[i], (dp[i][j], j))\n",
    "                    heappush(col_queues[j], (dp[i][j], i))\n",
    "        \n",
    "        return dp[m - 1][n - 1] if dp[m - 1][n - 1] < float('inf') else -1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minimumVisitedCells(self, grid):\n",
    "\t\tm = len(grid)\n",
    "\t\tn = len(grid[0])\n",
    "\t\tstep = 0\n",
    "\t\tcur = {(0,0)}\n",
    "\t\trows = [1] * m\n",
    "\t\tcols = [1] * n\n",
    "\t\trl = [set() for _ in range(m)]\n",
    "\t\tcl = [set() for _ in range(n)]\n",
    "\t\twhile cur:\n",
    "\t\t\tstep += 1\n",
    "\t\t\tif (m - 1, n - 1) in cur:\n",
    "\t\t\t\treturn step\n",
    "\t\t\tnxt = set()\n",
    "\t\t\tfor x, y in cur:\n",
    "\t\t\t\tif x < cols[y] - 1:\n",
    "\t\t\t\t\ttmp = set()\n",
    "\t\t\t\t\tfor x1 in cl[y]:\n",
    "\t\t\t\t\t\tif x < x1 <= x + grid[x][y]:\n",
    "\t\t\t\t\t\t\ttmp.add(x1)\n",
    "\t\t\t\t\t\t\tnxt.add((x1, y))\n",
    "\t\t\t\t\tcl[y] -= tmp\n",
    "\t\t\t\tt = min(x + grid[x][y] + 1, m)\n",
    "\t\t\t\tfor x1 in range(x - 1, cols[y] - 1, -1):\n",
    "\t\t\t\t\tif x1 + grid[x1][y] >= t or y + grid[x1][y] >= rows[x1]:\n",
    "\t\t\t\t\t\tcl[y].add(x1)\n",
    "\t\t\t\t\t\tt = x1\n",
    "\t\t\t\t\tif rl[x1]:\n",
    "\t\t\t\t\t\tfor y1 in rl[x1]:\n",
    "\t\t\t\t\t\t\tif y < y1 < y + grid[x1][y]:\n",
    "\t\t\t\t\t\t\t\tcl[y].add(x1)\n",
    "\t\t\t\t\t\t\t\tt = x1\n",
    "\t\t\t\t\t\t\t\tbreak\n",
    "\t\t\t\tfor x1 in range(max(x + 1, cols[y]), min(x + grid[x][y] + 1, m)):\n",
    "\t\t\t\t\tnxt.add((x1, y))\n",
    "\t\t\t\tcols[y] = max(cols[y], x + grid[x][y] + 1)\n",
    "\t\t\t\tif y < rows[x] - 1:\n",
    "\t\t\t\t\ttmp = set()\n",
    "\t\t\t\t\tfor y1 in rl[x]:\n",
    "\t\t\t\t\t\tif y < y1 <= y + grid[x][y]:\n",
    "\t\t\t\t\t\t\ttmp.add(y1)\n",
    "\t\t\t\t\t\t\tnxt.add((x, y1))\n",
    "\t\t\t\t\trl[x] -= tmp\n",
    "\t\t\t\tt = min(y + grid[x][y] + 1, n)\n",
    "\t\t\t\tfor y1 in range(y - 1, rows[x] - 1, -1):\n",
    "\t\t\t\t\tif y1 + grid[x1][y] >= t or x + grid[x][y1] >= cols[y1]:\n",
    "\t\t\t\t\t\trl[x].add(y1)\n",
    "\t\t\t\t\t\tt = y1\n",
    "\t\t\t\t\tif cl[y1]:\n",
    "\t\t\t\t\t\tfor x1 in cl[y1]:\n",
    "\t\t\t\t\t\t\tif x < x1 < x + grid[x1][y]:\n",
    "\t\t\t\t\t\t\t\trl[x].add(y1)\n",
    "\t\t\t\t\t\t\t\tt = y1\n",
    "\t\t\t\t\t\t\t\tbreak\n",
    "\t\t\t\tfor y1 in range(max(y + 1, rows[x]), min(y + grid[x][y] + 1, n)):\n",
    "\t\t\t\t\tnxt.add((x, y1))\n",
    "\t\t\t\trows[x] = max(rows[x], y + grid[x][y] + 1)\n",
    "\t\t\tcur = nxt\n",
    "\t\treturn -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        inf = 0x3f3f3f3f\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rows = [[] for _ in range(m)]\n",
    "        cols = [[] for _ in range(n)]\n",
    "        dp = [[inf] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == j == 0:\n",
    "                    heappush(rows[i], [1, i, j])\n",
    "                    heappush(cols[j], [1, i, j])\n",
    "                    step = 1\n",
    "                elif i == 0:\n",
    "                    h = rows[i]\n",
    "                    while h and grid[h[0][1]][h[0][2]] + h[0][2] < j:\n",
    "                        heappop(h)\n",
    "                    if h:\n",
    "                        step = h[0][0] + 1\n",
    "                    else:\n",
    "                        step = inf\n",
    "                    heappush(rows[i], [step, i, j])\n",
    "                    heappush(cols[j], [step, i, j])\n",
    "                elif j == 0:\n",
    "                    h = cols[j]\n",
    "                    while h and grid[h[0][1]][h[0][2]] + h[0][1] < i:\n",
    "                        heappop(h)\n",
    "                    if h:\n",
    "                        step = h[0][0] + 1\n",
    "                    else:\n",
    "                        step = inf\n",
    "                    \n",
    "                    heappush(rows[i], [step, i, j])\n",
    "                    heappush(cols[j], [step, i, j])\n",
    "                else:\n",
    "                    h = rows[i]\n",
    "                    while h and grid[h[0][1]][h[0][2]] + h[0][2] < j:\n",
    "                        heappop(h)\n",
    "                    if h:\n",
    "                        step = h[0][0] + 1\n",
    "                    else:\n",
    "                        step = inf\n",
    "                    \n",
    "                    h = cols[j]\n",
    "                    while h and grid[h[0][1]][h[0][2]] + h[0][1] < i:\n",
    "                        heappop(h)\n",
    "                    if h:\n",
    "                        step = min(step, h[0][0] + 1)\n",
    "                    else:\n",
    "                        step = min(step, inf)\n",
    "                    \n",
    "                    heappush(rows[i], [step, i, j])\n",
    "                    heappush(cols[j], [step, i, j])\n",
    "                dp[i][j] = step\n",
    "        return -1 if dp[-1][-1] >= inf else dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = {i : i for i in range(n)}\n",
    "    \n",
    "    def find(self, node):\n",
    "        path = []\n",
    "        # print(self.parent)\n",
    "        while node != self.parent[node]:\n",
    "            path.append(node)\n",
    "            node = self.parent[node]\n",
    "        for p in path:\n",
    "            self.parent[p] = node \n",
    "        return node \n",
    "    \n",
    "    def union(self, n1, n2):\n",
    "        p1 = self.find(n1)\n",
    "        p2 = self.find(n2)\n",
    "        if p1 != p2:\n",
    "            self.parent[p1] = p2 \n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rows = [UnionFind(n + 1) for _ in range(m)]\n",
    "        cols = [UnionFind(m + 1) for _ in range(n)]\n",
    "        queue = [0]\n",
    "        step = 1\n",
    "        while queue:\n",
    "            new = []\n",
    "            for coor in queue:\n",
    "                if coor == m * n - 1:\n",
    "                    return step\n",
    "                i, j = coor // n, coor % n \n",
    "                left, right = min(j + 1, n - 1), min(j + grid[i][j], n - 1)\n",
    "                left = rows[i].find(left)\n",
    "                while left <= right:\n",
    "                    new.append(i * n + left)\n",
    "                    rows[i].union(left, left + 1)\n",
    "                    cols[left].union(i, i + 1)\n",
    "                    left = rows[i].find(left)\n",
    "                up, down = min(i + 1, m - 1), min(i + grid[i][j], m - 1)\n",
    "                up = cols[j].find(up)\n",
    "                while up <= down:\n",
    "                    new.append(up * n + j)\n",
    "                    cols[j].union(up, up + 1)\n",
    "                    rows[up].union(j, j + 1)\n",
    "                    up = cols[j].find(up)\n",
    "            queue = new \n",
    "            step += 1 \n",
    "        return - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx = [SortedList(range(n)) for _ in range(m)]\n",
    "        sy = [SortedList(range(m)) for _ in range(n)]\n",
    "\n",
    "        q = deque([(0, 0, 1)])\n",
    "        while q:\n",
    "            x, y, d = q.popleft()\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return d\n",
    "\n",
    "            # 向右\n",
    "            l, r = y + 1, min(grid[x][y] + y + 1, n)\n",
    "            idx = sx[x].bisect_left(l)\n",
    "            while idx < len(sx[x]) and sx[x][idx] < r:\n",
    "                q.append((x, sx[x].pop(idx), d + 1))\n",
    "            \n",
    "            # 向下\n",
    "            l, r = x + 1, min(grid[x][y] + x + 1, m)\n",
    "            idx = sy[y].bisect_left(l)\n",
    "            while idx < len(sy[y]) and sy[y][idx] < r:\n",
    "                q.append((sy[y].pop(idx), y, d + 1))    \n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx = [SortedList(range(n)) for _ in range(m)]\n",
    "        sy = [SortedList(range(m)) for _ in range(n)]\n",
    "\n",
    "        q = deque([(0, 0, 1)])\n",
    "        while q:\n",
    "            x, y, d = q.popleft()\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return d\n",
    "\n",
    "            # 向右\n",
    "            l, r = y + 1, min(grid[x][y] + y + 1, n)\n",
    "            idx = sx[x].bisect_left(l)\n",
    "            while idx < len(sx[x]) and sx[x][idx] < r:\n",
    "                q.append((x, sx[x][idx], d + 1))\n",
    "                sx[x].pop(idx)\n",
    "            \n",
    "            # 向下\n",
    "            l, r = x + 1, min(grid[x][y] + x + 1, m)\n",
    "            idx = sy[y].bisect_left(l)\n",
    "            while idx < len(sy[y]) and sy[y][idx] < r:\n",
    "                q.append((sy[y][idx], y, d + 1))\n",
    "                sy[y].pop(idx)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = deque([(0, 0, 1)])\n",
    "        rows = [SortedList(list(range(n))) for _ in range(m)]\n",
    "        cols = [SortedList(list(range(m))) for _ in range(n)]\n",
    "        while q:\n",
    "            # print(q)\n",
    "            for _ in range(len(q)):\n",
    "                x, y, step = q.popleft()\n",
    "                if x == m - 1 and y == n - 1:\n",
    "                    return step\n",
    "                if grid[x][y]:\n",
    "                    r = rows[x]\n",
    "                    maxc = y + grid[x][y]\n",
    "                    ind = r.bisect_right(y)\n",
    "                    while ind < len(r) and r[ind] <= maxc:\n",
    "                        q.append((x, r[ind], step + 1))\n",
    "                        r.remove(r[ind])\n",
    "                    \n",
    "                    c = cols[y]\n",
    "                    maxr = x + grid[x][y]\n",
    "                    ind = c.bisect_right(x)\n",
    "                    while ind < len(c) and c[ind] <= maxr:\n",
    "                        q.append((c[ind], y, step + 1))\n",
    "                        c.remove(c[ind])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        if n > m:\n",
    "            grid = [[grid[j][i]  for j in range(n)] for i in range(m)]\n",
    "            n, m = m, n\n",
    "        res = [[999999999 for j in range(m)] for i in range(n)]\n",
    "        res[0][0] = 1\n",
    "        lst = [[0, 0, res[0][0]]]\n",
    "        lfts = [SortedList([i for i in range(m)]) for i in range(n)]\n",
    "        lfts[0].remove(0)\n",
    "        c_lfts = [SortedList([i for i in range(n)]) for i in range(m)]\n",
    "        c_lfts[0].remove(0)\n",
    "\n",
    "        while len(lst) != 0:\n",
    "            nst = []\n",
    "            # print(\"lst\", lst)\n",
    "            for x,y,v in lst:\n",
    "                if grid[x][y] == 0:\n",
    "                    continue\n",
    "                # to right\n",
    "                # print(\"x, y, v\", x, y, v)\n",
    "                yl = y + 1\n",
    "                yr = y + grid[x][y]\n",
    "                yl_idx = lfts[x].bisect_left(yl)\n",
    "                yr_idx = lfts[x].bisect_left(yr)\n",
    "                dels = []\n",
    "                while yl_idx <= yr_idx:\n",
    "                    if yl_idx < len(lfts[x]) and yl <= lfts[x][yl_idx] <= yr:\n",
    "                        dels.append([x, lfts[x][yl_idx]])\n",
    "                    yl_idx += 1\n",
    "                # print(\"--yl, yr =\", yl, yr, \"dels:\", dels)\n",
    "                # to down\n",
    "                xl = x + 1\n",
    "                xr = x + grid[x][y]\n",
    "                xl_idx = c_lfts[y].bisect_left(xl)\n",
    "                xr_idx = c_lfts[y].bisect_left(xr)\n",
    "                # dels = []\n",
    "                # print(\"c_lfts[y] is\", c_lfts[y], xl_idx, xr_idx)\n",
    "                while xl_idx <= xr_idx:\n",
    "                    if xl_idx < len(c_lfts[y]) and xl <= c_lfts[y][xl_idx] <= xr:\n",
    "                        # print(\"add\", [c_lfts[y][xl_idx], y])\n",
    "                        dels.append([c_lfts[y][xl_idx], y])\n",
    "                    xl_idx += 1\n",
    "                # print(\"--xl, xr =\", xl, xr, \"dels:\", dels)\n",
    "                for nx, ny in dels:\n",
    "                    # print(lfts, nx, ny)\n",
    "                    lfts[nx].remove(ny)\n",
    "                    c_lfts[ny].remove(nx)\n",
    "                    nst.append([nx, ny, v + 1])\n",
    "                    res[nx][ny] = v + 1\n",
    "\n",
    "            lst = nst\n",
    "\n",
    "        # for v in res:\n",
    "        #     print(v)\n",
    "\n",
    "\n",
    "        return res[-1][-1] if res[-1][-1] != 999999999 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        inf = float(\"inf\")\n",
    "        dis = [[inf]*n for _ in range(m)]\n",
    "        stack = deque([[0, 0]])\n",
    "        row = [deque(list(range(n))) for _ in range(m)]\n",
    "        col = [deque(list(range(m))) for _ in range(n)]\n",
    "        dis[0][0] = 1\n",
    "\n",
    "        while stack:  # 使用0-1BFS模拟\n",
    "            i, j = stack.popleft()\n",
    "            d = dis[i][j]\n",
    "\n",
    "            x = grid[i][j]\n",
    "            if x == 0:\n",
    "                continue\n",
    "\n",
    "            q = row[i]\n",
    "            lst = deque()\n",
    "            while q and q[0] < j:  # 取出左面还没到达的\n",
    "                lst.append(q.popleft())\n",
    "\n",
    "            while q and q[0] <= j+x:\n",
    "                ind = q.popleft()\n",
    "                if dis[i][ind] == inf:\n",
    "                    dis[i][ind] = d+1\n",
    "                    stack.append([i, ind])\n",
    "                    if i == m-1 and ind == n-1:\n",
    "                        return d+1\n",
    "\n",
    "            while lst:\n",
    "                if dis[i][lst[0]] == inf:  # 放回左面还没到达的\n",
    "                    q.appendleft(lst.popleft())\n",
    "                else:\n",
    "                    lst.popleft()\n",
    "\n",
    "            q = col[j]\n",
    "            lst = deque()\n",
    "            while q and q[0] < i:  # 取出上面还没到达的\n",
    "                lst.append(q.popleft())\n",
    "            while q and q[0] <= i+x:\n",
    "                ind = q.popleft()\n",
    "                if dis[ind][j] == inf:\n",
    "                    dis[ind][j] = d+1\n",
    "                    stack.append([ind, j])\n",
    "                    if ind == m-1 and j == n-1:\n",
    "                        return d+1\n",
    "            while lst:\n",
    "                if dis[lst[0]][j] == inf:  # 放回上面还没到达的\n",
    "                    q.appendleft(lst.popleft())\n",
    "                else:\n",
    "                    lst.popleft()\n",
    "        ans = dis[-1][-1]\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "'''\n",
    "\n",
    "作者：liupengsay\n",
    "链接：https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/solution/er-xu-cheng-ming-jiu-xu-zui-python31069y-h5b8/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minimumVisitedCells(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        rows_sl = [SortedList() for _ in range(m)]\n",
    "        cols_sl = [SortedList() for _ in range(n)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j == 0:\n",
    "                    rows_sl[i].add((0, grid[i][j] + j))\n",
    "                    cols_sl[j].add((0, grid[i][j] + i))\n",
    "                    continue\n",
    "                # print(i, j, rows_sl, cols_sl)\n",
    "                while rows_sl[i] and rows_sl[i][0][1] < j:\n",
    "                    rows_sl[i].remove(rows_sl[i][0])\n",
    "                while cols_sl[j] and cols_sl[j][0][1] < i:\n",
    "                    cols_sl[j].remove(cols_sl[j][0])\n",
    "                min_val = 10 ** 9\n",
    "                if rows_sl[i]:\n",
    "                    min_val = min(min_val, rows_sl[i][0][0] + 1)\n",
    "                if cols_sl[j]:\n",
    "                    min_val = min(min_val, cols_sl[j][0][0] + 1)\n",
    "                dp[i][j] = min_val\n",
    "                # print(i, j, min_val)\n",
    "                rows_sl[i].add((min_val, grid[i][j] + j))\n",
    "                cols_sl[j].add((min_val, grid[i][j] + i))\n",
    "        # print(dp)\n",
    "        return dp[m - 1][n - 1] + 1 if dp[m - 1][n - 1] != 10 ** 9 else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
